package 题目集.线段树or树状数组.树状数组;

import java.util.Arrays;
import java.util.Scanner;

/**
 * https://www.acwing.com/problem/content/3665/ 给定一个长度为 n 的整数序列 a1,a2,…,an
 * 请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。 请问这个最大值是多少？
 * 相当于寻找左侧比自己小的，最大的上升子序列和。再让这个子序列和加上自己。我能想到线段树的解法. 这题也可以用前缀树状数组维护数轴左侧的最大值
 */
public class demo02_最大上升子序列和 {
	static long[] tree;
	static int[] sort;
	static int n;

	public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n = sc.nextInt();
        int[] arr = new int[n+1];
        tree=new long[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        sort=arr.clone();
        Arrays.sort(sort,1,sort.length);
        long ans=0;
        for(int i=1;i<=n;i++) {
        	int rank=Arrays.binarySearch(sort,1,sort.length,arr[i]);
        	long max=query(rank-1)+arr[i];
        	ans=Math.max(ans, max);
        	add(rank,max);
        }
        System.out.println(ans);
    }

	private static long query(int rank) {
		long ans=0;
		for(int i=rank;i>0;i-=i&-i) {
			ans=Math.max(ans, tree[i]);
		}
		return ans;
	}

	private static void add(int rank, long max) {
		for(int i=rank;i<=n;i+=i&-i) {
			tree[i]=Math.max(max, tree[i]);
		}
	}
}
